package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;
import cn.pugle.oj.catalog.StackProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 * 耐心排序算法
 * O(n log n)
 *
 * @author tzp
 * @since 2020/9/16
 */
public class LC300_1 implements DynamicProblem, StackProblem {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        int[] a = {10, 9, 2, 5, 3, 7, 101, 18};
        //           [2,3,7,101]
//        int[] a = {-2, -1};
//        int[] a = {2, 2};
        System.out.println(new LC300_1().lengthOfLIS(a));
    }
}
